// @algorithm @lc id=1000229 lang=cpp
// @title Ygoe9J

#include "algm/algm.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> temp;
    vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        int n = candidates.size();
        dfs(candidates, n, 0, target);
        return ans;
    }
    void dfs(vector<int> &candidates, int n, int index, int target) {
        if (target == 0) {
            ans.push_back(temp);
            return;
        }
        if (index >= n || target < 0) {
            return;
        }
        if (candidates[index] > target) {
            dfs(candidates, n, index + 1, target);
            return;
        }
        temp.push_back(candidates[index]);
        dfs(candidates, n, index, target - candidates[index]);
        temp.pop_back();
        dfs(candidates, n, index + 1, target);
        return;
    }
};